1. Field of the Invention
The present invention relates to a multicast routing method, for use in data communication networks such as Asynchronous Transfer Mode (ATM) network, which multicast tree branching occurs as near as possible to multiple destination nodes so that the overlapping effects of the multicast route can effectively reduce the network link consumption.
2. Description of the Prior Art
Asynchronous Transfer Mode (ATM) has emerged as a promising transfer technique of broadband networks for supporting multimedia, multicast communication services such as video teleconferencing and tele-education. To provide multimedia multicast communication services in ATM networks, many network functions have to be improved. Those include the signalling procedures, the connection management and switch architecture for cell copying and merging etc. The most important function required to provide multicast service may be the routing algorithm because it directly affects the network utilization and quality-of-service (QoS) provided to the applications. An efficient multicast routing scheme in ATM network has to be scalable and resource saving while guaranteeing various QoS requirements. Also, it must be simple especially for real time applications. Designing a multicast routing algorithm that satisfies all this requirements is quite challenging.
Most of conventional routing methods are minimizing the total bandwidth of tree-shaped route, and can be applied to the non-real time multicast applications of computer network. In general, a cost function is defined for each link of network reflecting the routing policy. Then the cost optimized tree-shaped route between a source node and destination nodes are computed. This problem is well known as minimum cost Steiner Trees that is NP-complete.
Thus, the conventional multicast routing method first simplifies the network as only constructed by source node and destination nodes, so that the computational complexity to find the multicast route is minimized. Thereafter, to find out the minimum cost tree-shaped route, the conventional methods added minimum cost link one by one until source node and all destination nodes are connected.
Even though, however, this network simplifying process used in conventional methods can alleviate the computational complexity required to find out minimum cost route, it suffers from a drawback that some information is lost about the intermediate branching nodes. The branching nodes are the intermediate nodes that can be branch for two or more destination nodes. The branching (cell copying) effect can maximize the path overlapping effect between multiple destinations, so that minimize the network bandwidth consumption in the delivery of multicast information. Accordingly, the conventional multicast routing methods suffers from a shortcoming that it is performed without the reflection of a path overlapping effect, the total bandwidth consumption is increased.